

function initHead(arr = [], cur, ln) {
    let tmp = arr[cur];
    let j = cur;
    for (let i = 2 * cur + 1; i < ln; i = 2 * i + 1) {
        if (i < ln && arr[i] < arr[i + 1]) { // 先比较左右节点，
            i++; // 左节点比右节点小，就取右节点
        }
        if (tmp >= arr[i]) break; // 
        arr[cur] = arr[i];
        cur = i;
    }
    arr[cur] = tmp;
}

function headSort(arr = []) {
    let temp = 0;
    let len = arr.length;
    for (let i = parseInt(len / 2) - 1; i >= 0; i--) {
        initHead(arr, i, ln - 1);
    }
    for (let i = len - 1; i > 0; i--) {
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        initHead(arr, 0, i - 1);
    }
}